/**
 * LeetCode 124. 二叉树中的最大路径和
 */
public class Solution_124 {
    int maxSum = Integer.MIN_VALUE;

    /**
     * 官方题解：递归
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(n)
     */
    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }

    /**
     * 计算二叉树中的一个节点的最大贡献值
     * <p>
     * 在以该节点为根节点的子树中寻找以该节点为起点的一条路径，使得该路径上的节点值之和最大
     * <p>
     * 1. 空节点的最大贡献值等于 0
     * <p>
     * 2. 非空节点的最大贡献值等于节点值与其子节点中的最大贡献值之和（对于叶节点而言，最大贡献值等于节点值）。
     */
    public int maxGain(TreeNode node) {
        if (node == null) {
            return 0;
        }

        // 递归计算左右子节点的最大贡献值
        // 只有在最大贡献值大于 0 时，才会选取对应子节点
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);

        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int priceNewpath = node.val + leftGain + rightGain;
        // 更新答案
        maxSum = Math.max(maxSum, priceNewpath);
        // 返回节点的最大贡献值
        return node.val + Math.max(leftGain, rightGain);
    }
}
